//给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树不应
//该改变保留在树中的元素的相对结构（即，如果没有被移除，原有的父代子代关系都应当保留）。 可以证明，存在唯一的答案。 
//
// 所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。 
//
// 
//
// 示例 1： 
//
// 
//输入：root = [1,0,2], low = 1, high = 2
//输出：[1,null,2]
// 
//
// 示例 2： 
//
// 
//输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
//输出：[3,2,null,1]
// 
//
// 示例 3： 
//
// 
//输入：root = [1], low = 1, high = 2
//输出：[1]
// 
//
// 示例 4： 
//
// 
//输入：root = [1,null,2], low = 1, high = 3
//输出：[1,null,2]
// 
//
// 示例 5： 
//
// 
//输入：root = [1,null,2], low = 2, high = 4
//输出：[2]
// 
//
// 
//
// 提示： 
//
// 
// 树中节点数在范围 [1, 104] 内 
// 0 <= Node.val <= 104 
// 树中每个节点的值都是唯一的 
// 题目数据保证输入是一棵有效的二叉搜索树 
// 0 <= low <= high <= 104 
// 
// Related Topics 树 深度优先搜索 二叉搜索树 二叉树 
// 👍 438 👎 0

package com.cute.leetcode.editor.cn;
public class TrimABinarySearchTree {
    public static void main(String[] args) {
        Solution solution = new TrimABinarySearchTree().new Solution();
    }
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /**
     * 修剪二叉搜索树（左子树所有节点小于根节点的值，右子树所有节点大于根节点的值）
     * 注意，左右边界的值可能导致原来的根节点发生变化
     * @param root 根节点
     * @param low 左边界
     * @param high 右边界
     * @return 返回新的根节点
     */
    TreeNode res;
    public TreeNode trimBST(TreeNode root, int low, int high) {
        res = root;
        changeHead(res, low, high);
        cutTree(res, low, high);
        return res;
    }

    /**
     * 这是换根节点的方法，只要根节点不在目标区间就换
     */
    public void changeHead(TreeNode root,int low,int high){
        if (root == null) return;
        if (root.val>high) {
            res = root.left;
            changeHead(res,low,high);
        }
        else if (root.val<low){
            res = root.right;
            changeHead(res, low, high);
        }
    }

    /**
    * 这是剪枝的过程
     */
    public void cutTree(TreeNode root, int low, int high){
        if (root == null) return;
        if (root.left!=null && root.left.val<low){
            root.left = root.left.right;
            cutTree(root, low, high);
        }
        if (root.right!=null && root.right.val>high){
            root.right = root.right.left;
            cutTree(root, low, high);
        }
        cutTree(root.left, low, high);
        cutTree(root.right, low, high);
    }

    // 这是题解的版本，真的秀
    /*class Solution {
        public TreeNode trimBST(TreeNode root, int low, int high) {
            if (root == null) {
                return null;
            }
            if (root.val < low) {
                return trimBST(root.right, low, high);
            }
            if (root.val > high) {
                return trimBST(root.left, low, high);
            }
            // root在[low,high]范围内
            root.left = trimBST(root.left, low, high);//left接入合适的子树
            root.right = trimBST(root.right, low, high);
            return root;
        }
    }*/


}
//leetcode submit region end(Prohibit modification and deletion)

}